并不会有更好的阅读体验 甚至你在机房还访问不了
P3977 [TJOI2015]棋盘
你得知道题目下表是从 0 开始编号，那么每个棋子只能控制与它距离不大于 1 的行。
所以只需压当前这一行的状态，令 dp(i,S) 表示前 i 行棋子，第 i 的摆放状态为 S 的方案。
那么有转移：
CF208E Blood Cousins
和 u 拥有共同的 k 级祖先的点数就是 u 的 k 级祖先的 k 级儿子的数量 −1.
再转换一下就是以 u 的 k 级祖先为根的子树内深度为 depu+k 的点的个数−1。
然后用 cntd 表示深度为 d 的点数，直接 dsu on tree 即可。
P4035 [JSOI2008]球形空间产生器
设原形坐标为 O,圆上一点坐标为 A
由提示得：
UVA12177 First Knight
设 dp(i,j) 表示由 (i,j) 走到 (n,m) 的期望步数。
那么显然有转移：
CF685B Kay and Snowflake
这道题应该算是 CSP2019 树的重心 的前置知识了吧。可惜之前我并没有做过。
对于一棵以 u 为根的子树，它的重心只可能在点 u 或 以点 u 的重儿子为根的子树中。
那么类比 lca 倍增父亲，树的重心倍增重儿子。
UVA10859 Placing Lampposts
n 个点 m 条边的无向无环图，其实就是一个森林。
题目要求最小化两个量：灯数和只被一边照亮的边数。
一个做法是定义两个 dp 数组，分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。
P6218 [USACO06NOV] Round Numbers S
首先有个想法，如果该位为 0 且不是前导 0，则将 0 的数量加一，最后看 0 是否出现了至少 ⌈2len⌉ 次。
但这样有个问题，比如在 n=8(1000)2 时， 2(0010) 就不会被计入答案 ，原因是 2 的前导 0 也算在了它二进制的位数中。
所以还要记录前导零的数量 leadnum，最后判断是否出现至少 ⌈2len−leadnum⌉ 即可。
SP17247 Digit Sum
每个数的数字和的和其实就是所有数字与它出现次数的积的和。
那么对于 0−9 ，依次像 P2602 [ZJOI2010]数字计数 统计出现次数就可以了。
具体做法也很简单，记录前 pos 位某个数字出现次数 sum，记忆化搜索即可通过。
P4451 [国家集训队]整数的lqp拆分
设整数 n 的 lqp 拆分权值为 g(n) , 那么有：
0%